#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//定义最大顶点数，本常量在定义MGraph结构体的顶点和边时，都必须被用到
#define MVNum 100
typedef enum{FALSE,TRUE} Boolean;

typedef char VerTexType;      //假设顶点的数据类型为字符型
typedef int ArcType;          //假设边的权值类型为整型

typedef struct{
	VerTexType vexs[MVNum];     //顶点表
	ArcType arcs[MVNum][MVNum]; //邻接矩阵
	int vexnum, arcnum;         //图的当前点数和边数
} MGraph;

// ====查找图G的顶点的编号====
// 编号为构建图G时每个顶点的读入顺序，从0开始。
// 查找到指定顶点名字时，返回对应编号；找不到时，返回-1 。
int locate_vertex(MGraph * G, char vertex_name) {
	for (int i = 0; i < G->vexnum;++i) {
		if( vertex_name == G->vexs[i] ){
			return i;
		}
	}
	return -1;
}

//=========建立邻接矩阵=======
// 参数 G_pp 是尚未被初始化的 (指向 (指向 MGraph 的指针) 的指针)
// 参数 graph_data_filename 是存储如下格式的图数据的文件名（字符串）：
/*
 * 顶点数 边数
 * 顶点名字序列（用a b c d e 等字符命名）
 * a b // 边1
 * a c // 边2
 * d e // 边3
 */
void create_graph(MGraph ** G_pp, char * graph_data_filename)
{
	FILE * fp;
	size_t len = 0;
	ssize_t read;
	
	int num_nodes, num_edges;
	*G_pp = (MGraph *) malloc(sizeof (MGraph));
	if(*G_pp==NULL){
		printf("初始化失败");
	}
	// 打开由 graph_data_filename变量 指定的文件名
	fp = fopen(graph_data_filename, "r");
	if (fp == NULL)
	{
		printf("失败");
		exit(EXIT_FAILURE);
	}
	
	// 从文件名由 graph_data_filename 变量所指定的文件里读取顶点数和边数
	// fscanf函数 的用法类似scanf
	fscanf(fp, "%d %d\n", &num_nodes, &num_edges);
	// 后续的内容读取参考上一句 fscanf 函数
	for (int i = 0; i < num_nodes; ++i) {
		fscanf(fp,"%c\n",&((*G_pp)->vexs[i]));
	}
	(*G_pp)->vexnum = num_nodes;
	(*G_pp)->arcnum  = num_edges;
	for (int i = 0; i < num_edges; ++i) {
		char j,k;
		fscanf(fp,"%c %c\n",&j,&k);
		int a = locate_vertex(*G_pp,j),b= locate_vertex(*G_pp,k);
		(*G_pp)->arcs[a][b]=1;
		(*G_pp)->arcs[b][a]=1;
	}
	// 实现开始：可以自行定义变量，但是不要删掉或者更改对fopen和fclose的调用
	
	// 如上，用fscanf从fp里读取字符
	
	// 实现结束
	
	// 关闭打开的文件
	fclose(fp);
}

//========dfs：深度优先遍历的递归算法======
// 参数 G：指向MGraph类型的变量的指针。
// 参数 i: 当前被访问的顶点 i。i是顶点在给出的 顶点名字序列 里从0开始的位置编号：比如顶点 b 在 顶点序列 a b c d e f中的位置编号是 1。
// 参数 result_sequence: 用于记录在 当全局访问顺序为 visited_order 时，被访问的结点名字（字符）。
// 参数 visited_order: 当前顶点被访问的全局顺序
void dfs(MGraph *G, int i, Boolean visited[], char * result_sequence, int * visited_order)
{
	visited[i]=TRUE;
	char *s;
	s=(char *) malloc(2);
	s[0]=G->vexs[i];
	s[1]='\0';
	*visited_order=G->vexs[i];
	strcat(result_sequence,s);
	for (int j=0 ;j<G->vexnum;j++) {
		if(G->arcs[i][j]==1 && visited[j]==FALSE){
			dfs(G,j,visited,result_sequence,visited_order);
		}
	}
}

//===========bfs：广度优先遍历=======
// 参数 G：指向MGraph的指针
// 参数 k: 当前被访问的顶点 k。k是顶点在给出的 顶点名字序列 里从0开始的位置编号；比如顶点 b 在 顶点序列 a b c d e f中的位置编号是 1。
// 参数 visited_sequence: 用于记录在广度优先遍历时，依次被访问的顶点的名字（字符）
void bfs(MGraph *G, int k, Boolean visited[], char * visited_sequence)
{        char *s;
	s=(char *) malloc(2);
	s[0]=G->vexs[k];
	s[1]='\0';
	visited[k] = TRUE;
	strcat(visited_sequence,s);
	char str=*visited_sequence;
	int i =0;
	while (str!='\0'){
		for(int j = 0;j<G->vexnum;j++) {
			if (G->arcs[k][j] == 1 && visited[j] == FALSE) {
				visited[j] = TRUE;
				char *s;
				s = (char *) malloc(2);
				s[0] = G->vexs[j];
				s[1] = '\0';
				strcat(visited_sequence, s);
			}
		}
		i++;
		str = *(visited_sequence+i);
		if(str!='\0')
			k = locate_vertex(G,str);
	}
}

// 以下 main 函数的实现，供参考。

int main () {
	int i;
	MGraph *G;
	Boolean visited[MVNum];
	
	create_graph(&G, "graph_data.txt"); //建立邻接矩阵
	
	for(i=0; i<MVNum; i++) {
		visited[i] = FALSE;
	}
	char dfs_sequence[MVNum] = {'\0'};
	int visited_order = 0;
	dfs(G, 0, visited, dfs_sequence, &visited_order); //深度优先遍历。 应该输出：abdhecfg
	printf("Print Graph DFS: ");
	printf("%s\n", dfs_sequence);
	printf("\n");
	
	
	for(i=0; i<MVNum; i++) {
		visited[i] = FALSE;
	}
	char bfs_sequence[MVNum] = {'\0'};
	bfs(G, 0, visited, bfs_sequence); //以序号为0的顶点开始广度优先遍历。应该输出：abcdefgh
	printf("Print Graph BFS: ");
	printf("%s\n", bfs_sequence);
	printf("\n");
	for(i=0; i<MVNum; i++) {
		visited[i] = FALSE;
	}
	char bfs_sequence2[MVNum] = {'\0'};
	bfs(G, 3, visited, bfs_sequence2); //以序号为3的顶点开始广度优先遍历。应该输出：dbhaecfg
	printf("Print Graph BFS: ");
	printf("%s\n", bfs_sequence2);
	printf("\n");
	return 0;
}
